/**
 * @Project : ProgrammingExercises
 * @Package : Leetcode
 * @File : Q2521.java
 * @Author : WangRuoyu
 * @Date 2023/1/10 10:40
 */

package leetcode;

import java.util.HashSet;

public class Q2521 {
    static boolean isPrime(int num) {
        for (int k = 2; k <= num / k; k++) {
            if (num % k == 0) {
                return false;
            }
        }
        return true;
    }

    public int distinctPrimeFactors(int[] nums) {

        HashSet<Integer> set = new HashSet<>();

        for (int i = 0; i < nums.length; i++) {
            if (isPrime(nums[i])) {
                set.add(nums[i]);
            } else {
                int tmp = nums[i];

                for (int j = 2; j <= tmp / j; j++) {
                    if (isPrime(j)) {
                        if (tmp % j == 0) {
                            set.add(j);
                            while (tmp % j == 0) {
                                tmp /= j;
                            }
                        }
                    }
                }
                if (tmp != 1) {
                    set.add(tmp);
                }
            }
        }

        return set.size();
    }

    public static void main(String[] args) {
        Q2521 sl = new Q2521();
        int nums[] = {2, 4, 3, 7, 10, 6};
        System.out.println(sl.distinctPrimeFactors(nums));
    }
}